﻿//1234. 替换子串得到平衡字符串
//有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
//假如在该字符串中，这四个字符都恰好出现 n / 4 次，那么它就是一个「平衡字符串」。
//给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
//你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
//请返回待替换子串的最小可能长度。
//如果原字符串自身就是一个平衡字符串，则返回 0。



class Solution {
public:
    int balancedString(string s)
    {
        unordered_map<char, int> table;
        int n = s.size(), m = n / 4;
        for (auto& e : s)
        {
            table[e]++;
        }
        if (table['Q'] >= m && table['E'] >= m && table['W'] >= m && table['R'] >= m)
            return 0;
        int ans = n;
        int left = 0, right = -1;
        //使替换字符串最小  
        for (right = 0; right < s.size(); right++)
        {
            table[s[right]]--;
            while (table['Q'] <= m && table['E'] <= m && table['W'] <= m && table['R'] <= m)
            {
                ans = min(ans, right - left + 1);
                ++table[s[left++]];
            }
        }
        return ans;
    }
};